/**
 * 寻找二叉树中两个节点的最近公共祖先
 * 先序遍历
 */
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
 }

public class Solution {
    //保存最近公共祖先
    private static TreeNode commonTreeNode = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        commonTreeNode = null;
        preOrder(root, p, q);
        return commonTreeNode;
    }

    //整体采用先序遍历的方式
    private int preOrder(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return 0;
        }
        //记录公共节点的个数
        //0表示这棵树一个节点都没有
        //1表示这棵树有一个节点
        //2表示这棵树有两个节点，已经找到了最近公共祖先
        int count = 0;
        //如果当前节点就是其中一个节点，那么count + 1
        if(root.val == p.val || root.val == q.val) {
            count += 1;
        }
        //如果左子树的返回值 == 2,表示在遍历左子树时已经找到了公共节点，直接返回2
        int countLeft = preOrder(root.left, p, q);
        if(countLeft == 2) {
            return 2;
        }
        //右子树与左子树同理
        int countRight = preOrder(root.right, p, q);
        if(countRight == 2) {
            return 2;
        }
        //count的值只会等于0/1/2
        count = count + countLeft + countRight;
        //如果相加之后发现count == 2，说明当前的root就是最近公共祖先，需要保存
        if(count == 2) {
            commonTreeNode = root;
        }
        //返回遍历结果
        return count;
    }
}